package real.byteDance;

/**
 * 最长回文子串
 */
public class MostLongestStr {
    //对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
    //输入：
    //"ababc"
    //返回值：
    //3
    // 说明：
    //最长的回文子串为"aba"与"bab"，长度都为3
    public int getLongestPalindrome (String A) {
        int n = A.length();
        if (n == 0) return 0;
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            dp[i][i] = true; // 单个字符一定是回文
        }
        for (int l = 2; l <= n; l++) { // 子串长度
            for (int i = 0; i <= n - l; i++) {
                int j = i + l - 1;
                if (A.charAt(i) == A.charAt(j)) {
                    if (l == 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    dp[i][j] = false;
                }
                if (dp[i][j]) {
                    maxLen = Math.max(maxLen, l);
                }
            }
        }
        return maxLen;
    }


}
